package com.leetcode.专项突破.链表;

/**
 * @author 覃国强
 * @date 2022-03-24 10:02
 */
public class 双链表 {


  static
  class MyLinkedList {

    Node head;
    Node tail;

    int size;

    public MyLinkedList() {
      head = new Node();
      tail = new Node();
      head.next = tail;
      tail.prev = head;

      size = 0;
    }

    public int get(int index) {
      if (index < 0 || index >= size) {
        return -1;
      }

      Node node = head.next;
      while (index > 0) {
        node = node.next;
        --index;
      }
      return node.val;
    }

    public void addAtHead(int val) {
      Node node = new Node(val);
      node.next = head.next;
      node.prev = head;

      node.prev.next = node;
      node.next.prev = node;
      ++size;
    }

    public void addAtTail(int val) {
      Node node = new Node(val);
      node.next = tail;
      node.prev = tail.prev;

      node.prev.next = node;
      node.next.prev = node;
      ++size;
    }

    public void addAtIndex(int index, int val) {
      if (index == 0) {
        addAtHead(val);
      } else if (index == size) {
        addAtTail(val);
      } else if (index > 0 && index < size) {
        Node prevNode = head;
        while (index > 0) {
          prevNode = prevNode.next;
          --index;
        }
        Node node = new Node(val);
        node.next = prevNode.next;
        node.prev = prevNode;

        node.next.prev = node;
        node.prev.next = node;
        ++size;
      }
    }

    public void deleteAtIndex(int index) {
      if (index == 0 && size > 0) {
        deleteAtHead();
      } else if (index == size - 1 && size > 0) {
        deleteAtTail();
      } else if (index > 0 && index < size) {
        Node prevNode = head;
        while (index > 0) {
          prevNode = prevNode.next;
          --index;
        }

        Node deleteNode = prevNode.next;
        prevNode.next = deleteNode.next;
        prevNode.next.prev = prevNode;

        deleteNode.next = null;
        deleteNode.prev = null;
        --size;
      }
    }

    private void deleteAtTail() {
      if (size > 0) {
        Node deleteNode = tail.prev;
        deleteNode.prev.next = tail;
        tail.prev = deleteNode.prev;

        deleteNode.next = null;
        deleteNode.prev = null;
        --size;
      }
    }

    private void deleteAtHead() {
      if (size > 0) {
        Node deleteNode = head.next;
        head.next = deleteNode.next;
        head.next.prev = head;

        deleteNode.next = null;
        deleteNode.prev = null;
        --size;
      }
    }

    static class Node {
      int val;
      Node prev;
      Node next;

      Node() {}

      Node(int val) {
        this.val = val;
      }
    }

  }

}
